package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-24 14:32
 */
public class Pro1559 {
    private int find(int[] parent, int x) {
        while(parent[x] != x) {
            x = parent[x];
        }
        return x;
    }

    private boolean union(int[] parent, int x, int y) {
        int px = find(parent, x);
        int py = find(parent, y);
        if(px == py) return true;
        parent[py] = px;
        return false;
    }
    //利用并查集
    //i*len + j  表示点的根值，从左往右，从上往下找，发现相同的根值点的话，那么形成环，否则合并到并查集中
    public boolean containsCycle(char[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[] parent = new int[500 * 500];
        for(int i = 0; i < parent.length; i++) parent[i] = i;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                //上往下
                if(i > 0 && grid[i][j] == grid[i-1][j]) {
                    if(union(parent, i * m + j, (i-1) * m + j)) {
                        return true;
                    }
                }
                //
                if(j > 0 && grid[i][j-1] == grid[i][j]) {
                    if(union(parent, i * m + j - 1, i * m + j)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
